package leetcode

func reversePairs(nums []int) int {
	tmp := make([]int, len(nums))
	var sorted func(nums []int, low, high int) int
	sorted = func(nums []int, low, high int) int {
		if low >= high {
			return 0
		}
		mid := low + (high-low)/2
		res := sorted(nums, low, mid) + sorted(nums, mid+1, high)
		return res + merge(nums, tmp, low, mid, high)
	}
	return sorted(nums, 0, len(nums)-1)
}

func merge(nums, tmp []int, low, mid, high int) int {
	res := 0
	for i, j := low, mid+1; i <= mid; i++ {
		for j <= high && nums[i] > 2*nums[j] {
			j++
		}
		res += j - mid - 1
	}

	i, j, idx := low, mid+1, low
	for i <= mid && j <= high {
		if nums[i] <= nums[j] {
			tmp[idx], idx, i = nums[i], idx+1, i+1
		} else {
			tmp[idx], idx, j = nums[j], idx+1, j+1
		}
	}
	for i <= mid {
		tmp[idx], idx, i = nums[i], idx+1, i+1
	}
	for j <= high {
		tmp[idx], idx, j = nums[j], idx+1, j+1
	}

	for i = low; i <= high; i++ {
		nums[i] = tmp[i]
	}
	return res
}
